package snippet;
import java.util.*;
public class 组合总和 {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

    	backtracking(candidates,target,0);
    	
    	System.out.println(result);
    	return result;
    }
    
    public void backtracking(int[] candidates, int target,int index) {
    	if(sum > target) {
    		return;
    	}
    	if(sum == target) {
    		result.add(new ArrayList<>(item));
    		return;
    	}
    	
    	for(int i = index; i < candidates.length; i++) {
    		item.add(candidates[i]);
    		sum += candidates[i];
    		backtracking(candidates, target, i);
    		sum -= candidates[i];
    		item.remove(item.size() - 1);
    	}
    	
    }
    
    public static void main(String[] args) {
    	int nums[] = {2,3,5};
    	new 组合总和().combinationSum(nums, 8);
	}
}
